package lc;

import java.util.Arrays;

public class Q698 {

    public static void main(String[] args) {
        Q698 q698 = new Q698();
        System.out.println(q698.canPartitionKSubsets(new int[]{1,2,3,4,0,5}, 3));
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 先排序
        Arrays.sort(nums);
        // 计算总和
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int per = sum / k;
        // dfs算法计算
        // 创建一个数组，将数据一个一个放进去，如果满足条件了就继续放到下一个，如果一直到了最后一个，那么就是ok的
        return dfs(nums, 0, new int[k], k, per);
    }

    private boolean dfs(int[] nums,int index,int[] bucket, int k,int target) {
        if (index == nums.length) {
            return true;
        }
        for (int i = 0; i < k; i++) {
            // 当前桶等于target，直接过去？
            if (i > 0 && bucket[i] == bucket[i - 1]) continue;
            if (bucket[i] + nums[index] > target) {
                continue;
            }
            // 否则将当前数加到桶里，然后深度查询
            bucket[i] = bucket[i] + nums[index];
            if (dfs(nums, index + 1, bucket, k, target)) {
                return true;
            }
            bucket[i] = bucket[i] - nums[index];
        }
        return false;
    }




}
